﻿// 202 逆元1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>


using namespace std;
/*
http://oj.daimayuan.top/course/21/problem/490

给一个素数 p，求1∼n关于p的逆元。

由于输出可能很大，只需要求这些逆元的异或和即可。

输入格式
一行，两个整数p,n。

输出格式
一个整数，表示1到n这些数关于p的逆元的异或和。

样例输入
10007 1000
样例输出
14675
数据规模
对于所有数据，保证2≤p≤109+7,1≤n≤min(107,p−1)，并且p是素数。
*/

typedef long long ll;
const int N = 10100000;
ll inv[N];
int p, n;

int main()
{
	scanf("%d%d",&p,&n);
	inv[1] = 1;
	int ans = 1;
	for (int i = 2; i <= n; i++) {
		inv[i] = (p - p / i) * inv[p %i] % p;
		ans ^= inv[i];

	}

	printf("%d\n",ans);
}
 